package 栈;

import java.util.Stack;

public class No155最小栈 {

    /**
     * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
     * push(x) —— 将元素 x 推入栈中。
     * pop() —— 删除栈顶的元素。
     * top() —— 获取栈顶元素。
     * getMin() —— 检索栈中的最小元素。
     *  
     * 示例:
     * 输入：
     * ["MinStack","push","push","push","getMin","pop","top","getMin"]
     * [[],[-2],[0],[-3],[],[],[],[]]
     * 输出：
     * [null,null,null,null,-3,null,0,-2]
     * <p>
     * 解释：
     * MinStack minStack = new MinStack();
     * minStack.push(-2);
     * minStack.push(0);
     * minStack.push(-3);
     * minStack.getMin();   --> 返回 -3.
     * minStack.pop();
     * minStack.top();      --> 返回 0.
     * minStack.getMin();   --> 返回 -2.
     *  
     * 提示：
     * pop、top 和 getMin 操作总是在 非空栈 上调用。
     */

    static class MinStack {

        private Stack<Integer> stack;
        private Stack<Integer> sortStack;

        /**
         * initialize your data structure here.
         */
        public MinStack() {
            this.stack = new Stack<>();
            this.sortStack = new Stack<>();
        }

        public void push(int val) {
            this.stack.add(val);
            if (this.sortStack.isEmpty() || this.sortStack.peek() >= val) {
                this.sortStack.add(val);
            }
        }

        public void pop() {
            Integer popNum = this.stack.pop();
            if (popNum.equals(this.sortStack.peek())) {
                this.sortStack.pop();
            }
        }

        public int top() {
            return this.stack.peek();
        }

        public int getMin() {
            return this.sortStack.peek();
        }

    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        minStack.top();
        System.out.println(minStack.getMin());
    }

}
